# -*- coding:utf-8 -*-
List = list
# 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
# 求在该柱状图中，能够勾勒出来的矩形的最大面积。

# 示例 1:
# 输入：heights = [2,1,5,6,2,3]
# 输出：10
# 解释：最大的矩形为图中红色区域，面积为 10

# 示例 2:
# 输入： heights = [2,4]
# 输出： 4

# 提示：
# 1 <= heights.length <=105
# 0 <= heights[i] <= 104

# 错误思路：
# 数字升序的时候，下一个位置的最大面积可以根据前一个的最大面积比较获得
# eg: [5, 6]
# map[1] = max(map[0] + min(5, 6) + 6)

# class Solution:
#     def largestRectangleArea(self, heights: List[int]) -> int:
#         map = [0] * len(heights)
#         map[0] = heights[0]
#         for i in range(1, len(heights)):
#             if heights[i] >= heights[i - 1]:
#                 map[i] = max([heights[i], map[i - 1] + min(heights[i - 1], heights[i])])
#             else:
#                 map[i] = heights[i]
#                 l = i - 1
#                 while l >= 0:
#                     if heights[l] > heights[i]:
#                         map[i] += heights[i]
#                         l -= 1
#                         continue
#                     map[i] = max(map[i], map[l] + (i - l) * heights[l])
#                     break
#         ret = 0
#         for i in range(len(map)):
#             if map[i] > ret:
#                 ret = map[i]
#         return ret

# 超时
# 基本思路：第一遍遍历在第i位上，数字height[i]具有的最大面积，然后第二遍求出最大值
# class Solution:
#     def largestRectangleArea(self, heights: List[int]) -> int:
#         if heights == None:
#             return 0
        
#         h = [0] * len(heights)
#         minV = 10**5
#         for i in range(len(heights)):
#             if heights[i] < minV:
#                 minV = heights[i]
#             h[i] = heights[i]
#             l = i - 1
#             while l >= 0:
#                 if heights[l] == heights[i]:
#                     h[i] += h[l]
#                     break
#                 if heights[l] > heights[i]:
#                     h[i] += heights[i]
#                     l -= 1
#                     continue
#                 break
            
#         ret = 0        
#         for i in range(len(heights)):
#             ret = max(ret, h[i])
#             desc = heights[i]
#             l = i - 1
#             while l >= 0:
#                 if heights[l] <= desc:
#                     desc = heights[l]
#                     ret = max(ret, h[l] + (i - l) * heights[l])
#                 if heights[l] == minV:
#                     break
#                 l -= 1
#         return ret

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        if heights == None:
            return 0
        ls = []
        ret = 0
        cnt = len(heights)
        ls.append(-1)
        for i in range(cnt):
            while len(ls) > 1 and heights[i] < heights[ls[-1]]:
                ret = max(ret, heights[ls[-1]] * (i - ls[-2] - 1))
                ls.pop()
            ls.append(i)
        while len(ls) > 1:
            ret = max(ret, heights[ls[-1]] * (cnt - ls[-2] - 1))
            ls.pop()
        return ret

t = Solution()
# print(t.largestRectangleArea([2,1,5,6,2,3]))
# print(t.largestRectangleArea([2,4]))
# print(t.largestRectangleArea([1,2,3,4,5]))
# print(t.largestRectangleArea([2,3]))  
# print(t.largestRectangleArea([4,2,0,3,2,5]))  